\global\long\def\y{\mathbf{y}}


The ILP program above has an exponential number of (cycle)
constraints. Hence, simply passing the ILP to an off-the-shelf ILP
solver is not practical for all but the smallest sentences. For this
reason \citet{GermannFast04} only consider sentences of up to eight
tokens. However, recent work~\citep{riedel06incremental} has shown
that even exponentially large decoding problems may be solved
efficiently using ILP solvers if a Cutting-Plane
Algorithm~\citep{dantzig54solution} is used.%
\footnote{It is worth mentioning that Cutting Plane Algorithms have
  been successfully applied for solving very large instances of the
  Travelling Salesman Problem, a problem essentially equivalent to the
  decoding in IBM Model 4.}

% In the following we will present a Cutting Plane algorithm for IBM
% Model 4:
% \begin{enumerate}
% \item Construct ILP $I$ without cycle constraints

% \begin{enumerate}
% \item \textbf{do}

% \begin{enumerate}
% \item solve $I$ and assign to solution $\y$
% \item find cyclic paths in solution $\y$
% \item add corresponding cycle constraints to $I$
% \end{enumerate}
% \textbf{until} no more cyclic paths can be found

% \item \textbf{return} $\y$
% \end{enumerate}
% \end{enumerate}
A Cutting-Plane Algorithm starts with a subset of the complete set of
constraints. In our case this subset contains all but the
(exponentially many) cycle constraints. The corresponding ILP is
solved by a standard ILP solver, and the solution is inspected for
cycles. If it contains no cycles, we have found the true optimum: the
solution with highest score that does not violate any constraints. If
the solution does contain cycles, the corresponding constraints are
added to the ILP which is in turn solved again. This process is
continued until no more cycles can be found.

% It is difficult to make claims about a guaranteed worst-case runtime
% (or number of iterations) of this algorithm. However, if the linear
% scoring function (in other words, the translation model and language
% model parameters) already provides a preference for cycle-free solutions,
% we can expect this algorithm to be efficient. For example, if we assume
% that the translation/distortion model has a very strong preference
% for monotonic solutions then clearly the highest scoring solution
% is likely to be cycle-free.




%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "ilp-mt"
%%% End: 
